1444A - Division - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p;
int q,T;
vector<int> vc;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld %d",&p,&q);
		if(p % q)
		{
			printf("%lld\n",p);
			continue;
		}
		ll ans = 1;
		vc.clear();
		for(int i=2;i*i<=q;i++)
			if(q % i == 0)
				vc.push_back(i),vc.push_back(q/i);
		vc.push_back(q);
		for(int i=0;i<(signed)vc.size();i++)
		{
			ll r = p; 
			while(r % q == 0)	r /= vc[i];
			ans = max(ans,r);
		}
		printf("%lld\n",ans);
	}
 }